/*
 * @lc app=leetcode.cn id=2104 lang=typescript
 *
 * [2104] 子数组范围和
 */

// @lc code=start
function subArrayRanges(nums: number[]): number {
  // 计算当前位置前的区间和
  const getValue = (): number => {
    let res = 0;
    let pre_pos = -1;
    let i = 0;
    let j = 0;
    while (i < minQ.length) {
      let p = minQ[i];
      let q = maxQ[j];
      let cur_pos = Math.min(p, q);
      res += (cur_pos - pre_pos) * (nums[q] - nums[p]);
      if (p === cur_pos) i++;
      if (q === cur_pos) j++;
      pre_pos = cur_pos;
    }

    return res;
  };

  let n = nums.length;
  let ans = 0;
  // 单调队列，保存区间最小值的下标
  const minQ = [];
  // 单调队列，保存区间最大值的下标
  const maxQ = [];
  for (let i = 0; i < n; i++) {
    while (minQ.length && nums[i] <= nums[minQ[minQ.length - 1]]) {
      minQ.pop();
    }
    while (maxQ.length && nums[i] >= nums[maxQ[maxQ.length - 1]]) {
      maxQ.pop();
    }
    minQ.push(i), maxQ.push(i);
    // 计算当前位置前的区间和
    ans += getValue();
  }

  return ans;
}
// @lc code=end
